An important function performed by a computer system is to manage the resources, such as peripheral devices, an I/O port, memory, data structures, records, data, and files, allotted to a program or process while that process is running. Some resources are shareable among processes; that is, a process does not need mutually exclusive access to the resource to use it. The process uses the resource when needed and does not need to wait. Other resources are non-shareable; only one process can use that resource at a time. During that time, a mutually exclusive locking mechanism excludes all other processes from using the resource. If another process wants a busy resource, that process must wait until the resource becomes available.
Many data structures and searching programs manipulate records that are generally non-shareable between write and read processes. An example of such a data structure is an AVL (Adelson, Velskii, and Landis) tree. Programs that organize records in an AVL tree perform height-balancing operations after records are inserted or deleted from the tree. These balancing operations can cause incomplete (or intermediate) states to arise in the tree data structure. In computing environments having multiple central processing units (CPU) or running an operating system that uses preemptive scheduling, there can be several active processes vying for access to these records. In these environments, use of the AVL tree requires mutually exclusive locks to prevent processes from attempting to access a tree structure in an incomplete state. Consequently, these balancing operations can become a bottleneck and cause undesirable delays in process execution.